package 剑指offer.Month7_07.day14;

public class 二叉搜索树的后序遍历序列 {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        return solve(sequence,0,sequence.length-1);
    }

    public boolean solve(int[] sequence,int start,int end){
        if(start > end) return true;//如果此时的左节点大于右节点，证明遍历完毕
        int i = start;
        while(sequence[i] < sequence[end]) i++;
        for (int j = i;j < end;j++){
            if(sequence[j] < sequence[end]) return false;
        }
        return solve(sequence,start,i-1) && solve(sequence,i,end - 1);
    }
}
